Sphere decoding is a technique with a range of applications in the field of signal processing. Here particular reference will be made to applications of the technique to signals received over a MIMO (multiple-input multiple-output) channel, and to space-time decoding. However embodiments of the invention described herein may also be employed in related systems such as multi-user systems, and for other types of decoding, for example for a multi-user detector in a CDMA (code domain multiple access) system.
There is a continuing need for increased data rate transmission and, equivalently, for more efficient use of available bandwidth at existing data rates. Presently WLAN (wireless local area network) standards such as Hiperlan/2 (in Europe) and IEEE802.11a (in the USA) provide data rates of up to 54 Mbit/s. The use of multiple transmit and receive antennas has the potential to dramatically increase these data rates, but decoding signals received over a MIMO channel is difficult because a single receive antenna receives signals from all the transmit antennas. A similar problem arises in multi-user systems, although symbols transmitted over the different channels are then uncorrelated. There is therefore a need for improved decoding techniques for MIMO systems. These techniques have applications in wireless LANs, potentially in fourth generation mobile phone networks, and also in many other types of communication system.
FIG. 1a shows a typical MIMO data communications system 100. A data source 102 provides data (comprising information bits or symbols) to a channel encoder 104. The channel encoder typically comprises a convolutional coder such as a recursive systematic convolutional (RSC) encoder, or a stronger so-called turbo encoder (which includes an interleaver). More bits are output than are input, and typically the rate is one half or one third. The channel encoder 104 is followed by a channel interleaver 106 and, in the illustrated example, a space-time encoder 108. The space-time encoder 108 encodes an incoming symbol or symbols as a plurality of code symbols for simultaneous transmission from each of a plurality of transmit antennas 110.
Space-time encoding may be described in terms of an encoding machine, described by a coding matrix, which operates on the data to provide spatial and temporal transmit diversity; this may be followed by a modulator to provide coded symbols for transmission. Space-frequency encoding may additionally (or alternatively) be employed. Thus, broadly speaking, incoming symbols are distributed into a grid having space and time and/or frequency coordinates, for increased diversity. Where space-frequency coding is employed the separate frequency channels may be modulated onto OFDM (orthogonal frequency division multiplexed) carriers, a cyclic prefix generally being added to each transmitted symbol to mitigate the effects of channel dispersion.
The encoded transmitted signals propagate through MIMO channel 112 to receive antennas 114, which provide a plurality of inputs to a space-time (and/or frequency) decoder 116. The decoder has the task of removing the effect of the encoder 108 and the MIMO channel 112, and may be implemented by a sphere decoder. The output of the decoder 116 comprises a plurality of signal streams, one for each transmit antenna, each carrying so-called soft or likelihood data on the probability of a transmitted symbol having a particular value. This data is provided to a channel de-interleaver 118 which reverses the effect of channel interleaver 106, and then to a channel decoder 120, such as a Viterbi decoder, which decodes the convolutional code. Typically channel decoder 120 is a SISO (soft-in soft-out) decoder, that is receiving symbol (or bit) likelihood data and providing similar likelihood data as an output rather than, say, data on which a hard decision has been made. The output of channel decoder 120 is provided to a data sink 122, for further processing of the data in any desired manner.
In some communications systems so-called turbo decoding is employed in which a soft output from channel decoder 120 is provided to a channel interleaver 124, corresponding to channel interleaver 106, which in turn provides soft (likelihood) data to decoder 116 for iterative space-time (and/or frequency) and channel decoding. (It will be appreciated that in such an arrangement channel decoder 120 provides complete transmitted symbols to decoder 116, that is for example including error check bits.)
It will be appreciated that in the above described communication system both the channel coding and the space-time coding provide time diversity and thus this diversity is subject to the law of diminishing returns in terms of the additional signal to noise ratio gain which can be achieved. Thus when considering the benefits provided by any particular space-time/frequency decoder these are best considered in the context of a system which includes channel encoding.
One of the hardest tasks in the communications system 100 is the decoding of the space-time (or frequency) block code (STBC), performed by decoder 116, as this involves trying to separate the transmitted symbols that are interfering with one another at the receiver. The optimal STBC decoder is the a posteriori probability (APP) decoder, which performs an exhaustive search of all possible transmitted symbols. Such a decoder considers every transmitted symbol constellation point for all the transmit antennas and calculates all possible received signals, comparing these to the actually received signal and selecting that (those) with the closest Euclidian distance as the most likely solution(s). However the number of combinations to consider is immense even for a small number of antennas, a modulation scheme such as 16 QAM (quadrature amplitude modulation), and a channel with a relatively short time dispersion, and the complexity of the approach grows exponentially with the data rate. Sub-optimal approaches are therefore of technical and commercial interest.
Some common choices for space-time block decoding include linear estimators such as zero-forcing, and minimum mean-squared error (MMSE) estimators. The zero-forcing approach may be applied to directly calculate an estimate for a string of transmitted symbols or estimated symbols may be determined one at a time in a ‘nulling and cancelling’ method which subtracts out the effect of previously calculated symbols before the next is determined. In this way, for example, the symbols about which there is greatest confidence can be calculated first.
Sphere decoding or demodulation provides greatly improved performance which can approach that of an APP decoder, broadly speaking by representing the search space as a lattice (dependant upon the matrix channel response and/or space-time encoder) and then searching for a best estimate for a transmitted string of symbols only over possible string of symbols that generate lattice points which lie within a hypersphere of a given radius centred on the received signal. The maximum likelihood solution is the transmitted signal which, when modified by the channel, comes closest to the corresponding received signal. In fact the matrix channel response and/or space-time encoder tends to skew the input point space away from a rectangular grid and in a convenient representation the search region in the input point space becomes an ellipsoid rather than a sphere.
As the search space is reduced from the entire lattice to only a small portion of the lattice the number of computations required for the search is very much less than that required by an APP decoder, but similar results can be achieved. There are, however, some difficulties in practical application of such a procedure. Firstly one must identify which lattice points are within the required distance of the received signal. This is a relatively straightforward procedure, and is outlined below. Secondly, however, one must decide what radius to employ. This is crucial to the speed of the search and should be selected so that some, but not too many, lattice points are likely to be found within the radius. The radius may be adjusted according to the noise level and, optionally, according to the channel. However there is a further, more subtle problem which is that even with a known search radius the search problem is unbounded which, in a practical system, means that the time necessary for a sphere decoding calculation (and hence the available data rate) cannot be determined. This is one problem which is addressed by embodiments of the invention.
Background prior art relating to sphere decoding can be found in:
E. Agrell, T. Eriksson, A. Vardy and K. Zeger, “Closest Point Search in Lattices”, IEEE Transa. on Information Theory, vol. 48, no. 8, August 2002; E. Viterbo and J. Boutros, “A universal lattice code decoder for fading channels”, IEEE Trans. Inform. Theory, vol. 45, no. 5, pp. 1639-1642, July 1999; O. Damen, A. Chkeif and J. C. Belfiore, “Lattice code decoder for space-time codes,” IEEE Comms. Letter, vol. 4. no. 5, pp. 161-163, May 2000; B. M. Hochwald and S. T. Brink, “Achieving near capacity on a multiple-antenna channel,” http://mars.bell-labs.com/cm/ms/what/papers/listsphere/, December 2002; “On the expected complexity of sphere decoding”, in Conference Record of the Thirty-Fifth Asimolar Conference on Signals, Systems and Computers, 2001, vol. 2 pp. 1051-1055; B. Hassibi and H. Vikalo, “Maximum-Likelihood Decoding and Integer Least-Squares: The Expected Complexity”, in Multiantenna Channels: Capacity, Coding and Signal Processing, (Editors J. Foschini and S. Verdu), http://www.its.caltech.edu/˜hvikalo/dimacs.ps; A. M. Chan, “A New Reduced-Complexity Sphere Decoder For Multiple Antenna System”, IEEE International Conference on Communications, 2002, vol. 1, April-May 2002; L. Brunel, J. J. Boutros, “Lattice decoding for joint detection in direct-sequence CDMA systems”,IEEE Transactions on Information Theory, Volume: 49 Issue: 4, April 2003, pp. 1030-1037; A. Wiesel, X. Mestre, A. Pages and J. R. Fonollosa, “Efficient Implementation of Sphere Demodulation”, Proceedings of IV IEEE Signal Processing Advances in Wireless Communications, pp. 535, Rome, Jun. 15-18, 2003; U.S. Patent Application Number US20030076890 B. M. Hochwald and S. Ten Brink, filed Jul. 26, 2002, “Method and apparatus for detection and decoding of signals received from a linear propagation channel”, to Lucent Technologies, Inc; U.S. Patent Application Patent Number US20020114410 L. Brunel, filed Aug. 22, 2002, “Multiuser detection method and device in DS-CDMA mode”, to Mitsubishi; H. Vikalo, “Sphere Decoding Algorithms for Digital Communications”, PhD Thesis, Standford University, 2003; B. Hassibi and H. Vikalo, “Maximum-Likelihood Decoding and Integer Least-Squares: The Expected Complexity,” in Multiantenna Channels: Capacity, Coding and Signal Processing, (editors J. Foschini and S. Verdu).
The Agrell et al reference describes closest-point search methods for an infinite lattice where the input is an arbitrary m-dimensional integer, that is x ∈ Zm, reviewing the basic concept of lattice decoding and search methods, but only describing methods which provide a hard decision output. Most of the other references require the evaluation of a search region bound and nevertheless do not guarantee a bounded computational complexity calculation.
Wiesel et al describe one technique for determining a search radius by setting the search radius to the largest distance metric,
                    ∑                  n          =          1                          n          T                    ⁢              d        n        2              ,among the K symbols found by the search algorithm. Here, K is a predetermined number of symbols, say 50, required to evaluate a soft output. The initial search radius is set to infinity until K symbols is found. When the list is full, i.e. K symbols found, the search radius is set to the largest distance metric in the list. A heap sort is proposed as an efficient method to sort the candidate list, such that the list of candidates has K shortest distance metrics possible. This effectively acts as a set-up procedure. However again, depending upon the channel statistics the computational complexity of this method is not bounded.
Other decoders or detectors (here the terms are employed substantially synonymously since both imply an attempt to solve a similar problem, that is detecting the originally transmitted data) include trellis-based decoders such as the Viterbi decoder (which have exponential computational complexity), and reduced complexity detectors which provides sub-optimum performance, such as the vertical BLAST (Bell labs LAyered Space Time) decoder and the block decision feedback equalizer.
It is helpful, at this point, to provide an outline review of the operation of the sphere decoding procedure. For a string of N transmitted symbols an N-dimensional lattice is searched, beginning with the Nth dimensional layer (corresponding to the first symbol of the string). A symbol is selected for this layer from the constellation employed and the distance of the generated lattice point from the received signal is checked. If the lattice point is within this distance the procedure then chooses a value for the next symbol in the string and checks the distance of the generated lattice point from the received signal in N-1 dimensions. The procedure continues checking each successive symbol in turn, and if all are within the bound it eventually converges on a lattice point in one dimension. If a symbol is outside the chosen radius then the procedure moves back up a layer (dimension) and chooses the next possible symbol in that layer (dimension) for checking. In this way the procedure builds a tree in which the lowest nodes correspond to complete strings of symbols and in which the number of nodes at the nth level of the tree corresponds to the number of lattice points inside the relevant nth dimensional sphere.
When a complete candidate string of symbols is found the distance of the lattice point, generated from the string of symbols, from the received signal is found and the initial radius is reduced to this distance so that as the tree builds only closer strings to the maximum-likelihood solution are identified. When the tree has been completed the decoder can be used to provide a hard output, i.e. the maximum likelihood solution, by choosing the nearest lattice point to the received signal. Alternatively a soft output can be provided using a selection of the closest lattice points to the received signal, for example using the distance of each of these from the received signal as an associated likelihood value. A heap sort has been proposed for selecting a subset of candidates having lattice point with the shortest distance metrics to the received signal as described further below. Another proposed method sets a fixed search radius throughout the search and a subset of candidates providing distance metrics less than the fixed search radius is selected.